\chapter{IA, recherche de solution}

\section{Présentation}
Dans cette partie nous allons vous expliquer en détail comment fonctionne notre IA, et les choix que nous avons faits dans l'implémentation de celle-ci.

\subsection{Structure de données}
Tout d'abord, la structure de données que nous utilisons pour résoudre le jeu se compose de deux tables de hachage et d'une pile. Les tables de hachages nous servent à modéliser un arbre, tandis que la pile a pour fonction d'indiquer à l'utilisateur le chemin à effectuer pour arriver à la solution.

La première table de hachage prend pour \emph{Key} une chaine de caractères qui représente la position de tout les robots à un instant T, et pour \emph{Value} un entier correspondant à la profondeur de la première occurrence de cette configuration. 

La seconde table hachage à comme \emph{Key} la même chaine de caractères, mais comme \emph{Value} la position des robots "père".

La pile contient l'ensemble des clés qui composent le chemin solution.

\subsection{Système de clé}
Comme dit plus haut, la \emph{Key} des tables de hachage est une chaine de caractères spéciale contenant la position des robots à un instant donné.

La chaine de caractères est de la forme : 

\emph{PositionXRobotBleu;PositionYRobotBleu;Bleu\&PositionXRobotVert;…}

\subsection{Avantages}
Nous avons choisi d'implémenter notre IA en utilisant des tables de hachage car elles permettent de s'assurer de l'unicité des \emph{Keys}. C'est un point très important car si une configuration de robots apparait alors qu'elle est déjà dans la table de hachage cela signifie qu'elle a déjà été traitée et que donc il n'est pas nécessaire de la retraiter. Cela permet de réduire grandement le nombre de cas à traiter à chaque profondeur.

De plus, nous avons choisi d'utiliser une chaine de caractères comme \emph{Key} pour les tables de hachage plutôt que la liste de tous les robots car il est plus facile et plus efficace de comparer deux chaines de caractères plutôt que deux listes d'objets.

\section{Recherche de la solution}

\subsection{Initialisation}
Lors de l'initialisation de notre algorithme, la position courante des robots est transmise à notre algorithme. Il crée alors la clé racine qu'il ajoute dans la première table de hachage à la profondeur 0.

\subsection{Itération}
Par la suite, tant que la solution n'a pas été trouvée nous répétons les étapes suivantes :

\begin{itemize}
\item Nous récupérons l'ensemble des \emph{Keys} qui ont pour \emph{Value} depth-1 (c'est-à-dire toutes les clés ajoutées lors de la précédente itération)

\item Chaque clé est ensuite décomposée de façon à obtenir la configuration des robots associée.

\item Chaque robot est déplacé dans toutes les directions dans lesquelles il peut bouger. C'est-à-dire dans toutes les directions où il n'est pas obstrué par un mur ou un autre robot.

\item Pour chaque déplacement du robot nous reconstruisons la clé associée à cette nouvelle configuration du plateau.

\item Si ce déplacement est un déplacement gagnant, la clé est conservée comme étant la feuille de l'arbre et sera utilisée pour la reconstruction du chemin parcouru.

\item Sinon, on ajoute cette clé dans la table de hachage en s'assurant qu'elle n'y soit pas déjà. Si elle n'y est pas, on l'ajoute également dans la seconde table de hachage servant à reconstruire la solution, avec comme \emph{Value} la clé père.
\end{itemize}

\subsection{Reconstruction du chemin}
Une fois la solution trouvée, nous remontons de père en fils grâce à la seconde table de hachage, et nous stockons à chaque itération la clé fils dans la première pile. 

Ensuite, nous comparons deux a deux les clés contenues dans pile, pour pouvoir retrouver la direction dans laquelle s'est déplacé le robot entre sa première et sa seconde position. Cette opération à pour but d'indiquer à l'utilisateur la direction dans laquelle doit déplacer le robot.

\section{Amélioration possible}
La version actuelle de notre algorithme nous permet de traiter un maximum d'environ un million de possibilités différentes, ce qui permet de trouver des solutions en environ 15 coups maximum.

Une amélioration possible serait de créer un algorithme qui attribuerait un poids aux possibilités de la profondeur d'arrêt. Cette pondération serait utilisée pour déterminer quelle possibilité peut être utilisée pour relancer l'algorithme.
